package main;

import java.util.*;

public class CacheEntry extends MemoryUnit{
	
	ArrayList<Integer> tags;
	Object[] data;
	boolean[] dirty;
	
	public CacheEntry(int m, int l) {
		tags = new ArrayList<Integer>();
		data = new Object[m*(l/2)];
		dirty = new boolean[m];
	}
	
	static void writeToCache(int address,Object x, int depth, boolean f) {
		
		if(depth > n_cache_levels) {
			if(f) Cycles.value+=n_data_mem;
			if(x instanceof Integer) DataMemory.put(address, (Integer)x);
			else IMemory.put(address, (Instruction)x);
			return;
		}
		
		if(f) {
			Cycles.value+=cache_cycles[depth-1];
			cache_accesses[depth-1]++;
		}
		
		int d = address%(l[depth-1]/2);
		int i = (address/(l[depth-1]/2))%(C[depth-1]/m[depth-1]);
		int tag = (address/(l[depth-1]/2))/(C[depth-1]/m[depth-1]);
		int lx = l[depth-1]/2;
		
		CacheEntry block;
		
		if(depth == 1 && x instanceof Integer) {block = D_Cache.get(i);}
		else if(depth == 1 && x instanceof Instruction) {block = I_Cache.get(i);}
		else if(depth == 2) {block = Cache2.get(i);}
		else {block = Cache3.get(i);}
		
		ArrayList<Integer> myTags = block.tags;
		int tagPosition = myTags.indexOf(tag);
		
		boolean filled = false;
		
		if(tagPosition != -1){ 
			Object xx = block.data[(tagPosition*lx)+d];	
			filled = ((xx instanceof Integer && x instanceof Integer)
					|| (xx instanceof Instruction && x instanceof Instruction));
		}
		
		if(filled && f && x instanceof Integer) {
			
			cache_hit[depth-1]++;
		}
		
		if(tagPosition != -1 && (writingPolicy_miss[depth-1] || filled)) {
			
			block.data[(tagPosition*lx)+d] = x;
			
			
			if(!writingPolicy_hit[depth-1]) {
				
				if(f) {
				
				boolean t1 = writingPolicy_miss[1];
				boolean t2 = writingPolicy_miss[2];
				
				writingPolicy_miss[1] = true;
				writingPolicy_miss[2] = true;
								
				for(int t=depth+1; t<=n_cache_levels+1; t++)
					writeToCache(address, x, t, false);
				
				writingPolicy_miss[1] = t1;
				writingPolicy_miss[2] = t2;
				
				}
			
			}
				
			else {
				block.dirty[tagPosition] = true;
			}
		}
		
		else if(block.tags.size() < m[depth-1] && writingPolicy_miss[depth-1]) {
			myTags.add(tag);
			tagPosition = myTags.indexOf(tag);
						
			block.data[(tagPosition*lx)+d] = x;
			
			if(!writingPolicy_hit[depth-1]) {
				
				if(f) {
					
					boolean t1 = writingPolicy_miss[1];
					boolean t2 = writingPolicy_miss[2];
					
					writingPolicy_miss[1] = true;
					writingPolicy_miss[2] = true;
									
					for(int t=depth+1; t<=n_cache_levels+1; t++)
						writeToCache(address, x, t, false);
					
					writingPolicy_miss[1] = t1;
					writingPolicy_miss[2] = t2;
					
					}
				
				
				}
			
			else {
				block.dirty[tagPosition] = true;
			}
		}
		else {
			lx = l[depth-1]/2;
			if(writingPolicy_miss[depth-1]) {
				
				int oldAddress = (myTags.get(0)*(C[depth-1]/m[depth-1])*lx)+(i*lx);
				boolean data = false;
				
				Object[] oldData = new Object [lx];
				for(int k=0;k<(lx);k++) {
					oldData[k] = block.data[k];
					data |= oldData[k] instanceof Integer;
					block.data[k] = null;
				}
				myTags.set(0, tag);
				block.data[d] = x;
				if(!writingPolicy_hit[depth-1]) {
					if(f) {
						
						boolean t1 = writingPolicy_miss[1];
						boolean t2 = writingPolicy_miss[2];
						
						writingPolicy_miss[1] = true;
						writingPolicy_miss[2] = true;
										
						for(int t=depth+1; t<=n_cache_levels+1; t++)
							writeToCache(address, x, t, false);
						
						writingPolicy_miss[1] = t1;
						writingPolicy_miss[2] = t2;
						
						}
					
				}
				
			if(block.dirty[0]){
					
				for(int t=depth+1; t<=n_cache_levels+1; t++){
					writeToCacheReadMiss(oldAddress, oldData, t, false, data);
					
				}
					sendToMemory(oldAddress, oldData);
				}
			}
			//writingPolicy_hit[0]|| writingPolicy_hit[1] ||writingPolicy_hit[2]
			else {
				writeToCache(address,x,depth+1,true);
			}
		}
		
	}
	
	static void writeToCacheReadMiss(int address,Object[] x, 
			int depth, boolean f, boolean data) {
		
		
		if(depth > n_cache_levels) {
			
			sendToMemory(address, x);
			return;
		}
		
		int d = address%(l[depth-1]/2);
		int i = (address/(l[depth-1]/2))%(C[depth-1]/m[depth-1]);
		int tag = (address/(l[depth-1]/2))/(C[depth-1]/m[depth-1]);
		
		int lx = l[depth-1]/2;
		
		CacheEntry block;
		
		if(depth == 1 && data) {block = D_Cache.get(i);}
		else if(depth == 1 && !data) {block = I_Cache.get(i);}
		else if(depth == 2) {block = Cache2.get(i);}
		else {block = Cache3.get(i);}
		
		ArrayList<Integer> myTags = block.tags;
		int tagPosition = myTags.indexOf(tag);
		
		int limit = Math.min((l[depth-1]/2),x.length+d);
		
		if(tagPosition != -1) {
			
			for(int k=d; k<limit; k++) 
				block.data[(tagPosition*lx) + k] = x[k-d];
		
			block.dirty[tagPosition] = false;
			
		}
		
		else if(block.tags.size() < m[depth-1]) {
			myTags.add(tag);
			tagPosition = myTags.indexOf(tag);
			
						
			for(int k=d; k<limit; k++){ 
				
				block.data[(tagPosition*lx) + k] = x[k-d];
			}
			block.dirty[tagPosition] = false;
			
			
		}
		else {
				
				int oldAddress = (myTags.get(0)*(C[depth-1]/m[depth-1])*lx)+(i*lx);
				
				Object[] oldData = new Object [lx];
				for(int k=0;k<(lx);k++) {
					oldData[k] = block.data[k];
					block.data[k] = null;
				}
				myTags.set(0, tag);
				
				for(int k=d; k<limit; k++) block.data[k] = x[k-d];
			
			if(f) return; 	
				
			if(block.dirty[0]){
					
					for(int t=depth+1; t<n_cache_levels; t++){
						writeToCacheReadMiss(oldAddress, oldData, t, true, data);
						
					}
					sendToMemory(oldAddress, oldData);
				}
			
			}
			//writingPolicy_hit[0]|| writingPolicy_hit[1] ||writingPolicy_hit[2]
			block.dirty[0] = false;
		
	}
	
	static Object readFromCache(int address, boolean data) {
		
		int d = address%(l[0]/2);
		int i = (address/(l[0]/2))%(C[0]/m[0]);
		int tag = (address/(l[0]/2))/(C[0]/m[0]);
		int lx = l[0]/2;
		
		if(data)cache_accesses[0]++;
		if(data) Cycles.value += cache_cycles[0];
		
		
		CacheEntry block;
		
		if(data) block = D_Cache.get(i);
		else block = I_Cache.get(i);
		
		ArrayList<Integer> myTags = block.tags;
		int tagPosition = myTags.indexOf(tag);
		boolean filled = false;
		
		if(tagPosition != -1){ 
			Object xx = block.data[(tagPosition*lx)+d];	
			filled = ((xx instanceof Integer && data)
					|| (xx instanceof Instruction && !data));
		}
		
		if(filled) {
			if(data) cache_hit[0]++;
			return block.data[(tagPosition*lx)+d];
			
		}
		else {
			Object x = null;
			int k;
			Object[] newData = null;
			for(k=2;k<4 && k<=n_cache_levels ;k++) {
				
				if(data) {
					Cycles.value+=cache_cycles[k-1];
					cache_accesses[k-1]++;
				}
				newData = new Object[m[k-1]*(l[k-1]/2)];
				lx = l[k-1]/2;
				d = address%(l[k-1]/2);
				i = (address/(l[k-1]/2))%(C[k-1]/m[k-1]);
				tag = (address/(l[k-1]/2))/(C[k-1]/m[k-1]);
				filled = false;
								
				if(k==2) block = Cache2.get(i);
				else block = Cache3.get(i);
				
				myTags = block.tags;
				tagPosition = myTags.indexOf(tag);
				
				if(tagPosition != -1){ 
					Object xx = block.data[(tagPosition*lx)+d];	
					filled = ((xx instanceof Integer && data)
							|| (xx instanceof Instruction && !data));
				}
				if(filled) {
					
					if(data) cache_hit[k-1]++;
					int limit = Math.min(m[k-1]*(l[k-1]/2),newData.length+d);
					
					for(int kk=d; kk<limit; kk++)
					newData[kk-d] = block.data[(tagPosition*lx) + kk];
					x = block.data[(tagPosition*lx) + d];
					break;
				}
			}
			
			if(x == null) {
				newData = new Integer[memory_block_size/2];
				
				if(data) Cycles.value+=n_data_mem;
								
				newData = getFromMemory(address,data);
				
				x = newData[0];
				k++;
			}
			k--;
			while(k > 0){
				
				writeToCacheReadMiss(address, newData, k--, false, data);
			}
			if(x == null) return 0;
			return x;
			
		}
						
	}
	
static int getCyclesICache(int address, int w) {
		
		CacheEntry block;
		
		ArrayList<Integer> myTags;
		boolean filled;
		
		int k;
		int n = 0;
		boolean[] hit = new boolean[3];
		
		for(int ii=0; ii<w; ii++){
									
		for(k=1;k<4 && k<=n_cache_levels ;k++) {
				
			int lx = l[k-1]/2;
			int d = address%(l[k-1]/2);
			int i = (address/(l[k-1]/2))%(C[k-1]/m[k-1]);
			int tag = (address/(l[k-1]/2))/(C[k-1]/m[k-1]);
								
			if(k==1) block = I_Cache.get(i);
			else if(k==2) block = Cache2.get(i);
			else block = Cache3.get(i);
			
			filled = false;
				
			myTags = block.tags;
			int tagPosition = myTags.indexOf(tag);
			Object xx = null;	
			
			if(tagPosition != -1){ 
					xx = block.data[(tagPosition*lx)+d];	
					filled = (xx instanceof Instruction);
			}
			if(filled) {
				hit[k-1]= true;
				break;
			}
					
		}
		address++;
		n = Math.max(n, k);
		
	}
		int cycles = 0;
		for(int ii=0; ii<n; ii++) {
			if(ii == n_cache_levels) cycles += n_data_mem;
			else {
				if(hit[ii]) cache_hit[ii]++;
				cycles+=cache_cycles[ii];
				cache_accesses[ii]++;
			}
		}
		
		
		return cycles;
}
	
	static void sendToMemory(int address, Object[] block) {
		
		//int d = address%(memory_block_size/2);
		//address -=d;
				
		for(int i=0;i<block.length;i++) {
			if(block[i] instanceof Integer) 
				DataMemory.put(address+i, (Integer) block[i]);
			else if(block[i] instanceof Instruction)
				IMemory.put(address+i, (Instruction) block[i]);
		}
		
	}
	
	static Object[] getFromMemory(int address, boolean data) {
		
		Object[] block = new Object [memory_block_size/2];
		
		//int d = address%(memory_block_size/2);
		//address -=d;
		
		
		for(int i=0;i<block.length;i++) {
			if(data) block[i]  = DataMemory.get(address+i);
			else block[i]  = IMemory.get(address+i);
		}
		
		return block;
		
	}
	
	
	static void initializeCaches() {
		
		for(int i=0;i<(C[0]/m[0]);i++) D_Cache.add(new CacheEntry(m[0],l[0]));
		for(int i=0;i<(C[0]/m[0]);i++) I_Cache.add(new CacheEntry(m[0],l[0]));
		
		if(n_cache_levels>=2)  for(int i=0;i<(C[1]/m[1]);i++) Cache2.add(new CacheEntry(m[1],l[1]));
		if(n_cache_levels == 3) for(int i=0;i<(C[2]/m[2]);i++) Cache3.add(new CacheEntry(m[2],l[2]));
		
	}
	
	static void PrintALLMemory() {
		
		System.out.println(DataMemory);
		System.out.println(IMemory);
		
		
		for(int e=0; e<n_cache_levels+1; e++){
		ArrayList<CacheEntry> ch;
		if(e==0) ch = D_Cache;
		else if(e==1) ch = Cache2;
		else if(e == 2) ch = Cache3;
		else ch = I_Cache;
		
		for(int i=0; i<ch.size(); i++){
		ArrayList<Integer> tags = ch.get(i).tags;
		Object[] data = ch.get(i).data;
		for(int j=0; j<tags.size(); j++) System.out.print(tags.get(j)+" ; ");
		System.out.println();
		for(int k=0; k<data.length; k++) System.out.print(data[k]+" ; ");
		System.out.println();
		}
		System.out.println("/////////////End Of Cache "+(e+1)+"//////////");	
		}
		
	}
	
	public static void main(String[] args) {
		
//		//Memory.put(4000, 12);
//		
//		Order ii = new Order(6);
//		LinkedList<Order> l = new LinkedList<Order>();
//		l.add(ii);
//		
//		Map<Integer,Order> test = new HashMap<Integer,Order>();
//		
//		test.put(4000, ii);
		Instruction i1 = new Instruction(1);
		Instruction i2 = new Instruction(1);
		Instruction i3 = new Instruction(1);
		Instruction i4 = new Instruction(1);
		
		DataMemory.put(4000, 100);
		DataMemory.put(4001, 101);
		DataMemory.put(4002, 102);
		DataMemory.put(4003, 103);
		DataMemory.put(4004, 104);
		DataMemory.put(4005, 105);
		DataMemory.put(4006, 106);
		DataMemory.put(4007, 107);
		DataMemory.put(4003, 103);
		IMemory.put(4000, i1);
		IMemory.put(4001, i2);
		IMemory.put(4002, i3);
		IMemory.put(4003, i4);

//		
//		ii.value++;
//		
//		//int i = DataMemory.get(4000);
//		System.out.println(test.get(4000).value+"---"+l.getFirst().value+"---"+ii.value);
//		
		S[0] = 128;
		l[0] = 4;
		C[0] = S[0]/l[0];
		m[0] = 4;
		
		S[1] = 256;
		l[1] = 8;
		C[1] = S[1]/l[1];
		m[1] = 4;
		
		S[2] = 512;
		l[2] = 16;
		C[2] = S[2]/l[2];
		m[2] = 4;
		
		n_cache_levels = 3;
		
		CacheEntry.initializeCaches();
		
		writingPolicy_hit[0] = true;
		writingPolicy_hit[1] = true;
		writingPolicy_hit[2] = true;
		
		writingPolicy_miss[0] = true;
		writingPolicy_miss[1] = true;
		writingPolicy_miss[2] = true;
		
		n_data_mem = 3;
		cache_cycles[0] = 1;
		cache_cycles[1] = 1;
		cache_cycles[2] = 2;
		
//		writeToCache(2000, 90, 1, true);
//		writeToCache(4000, 91, 1, true);
//		writeToCache(2002, 92, 1, true);
//		writeToCache(2003, 93, 1, true);
//		writeToCache(2004, 94, 1, true);
////		
//		writeToCache(2005, 1, 1, true);
//		writeToCache(2006, 2, 1, true);
//		writeToCache(2007, 3, 1, true);
//		writeToCache(2008, 4, 1, true);
////		
//		writeToCache(3027, 1111, 1, true);
////		
//		writeToCache(2008, 5, 1, true);
//		writeToCache(2010, 593, 1, true);
//		writeToCache(2016, 502, 1, true);
//		writeToCache(2028, 91, 1, true);
//		writeToCache(2106, 592, 1, true);
////		
//		readFromCache(4000, true);
//////////		
//		writeToCache(1025, 467, 1, true);
//		writeToCache(1126, 468, 1, true);
//		writeToCache(1027, 469, 1, true);
//////		
//		writeToCache(1005, 767, 1, true);		
//		
		n_data_mem = 3;
//		System.out.println(readFromCache(4004));
//		
//		//System.out.println(cache_accesses[0]+";"+cache_accesses[1]+";"+cache_accesses[2]);
//		System.out.println(Cycles);
//		Cycles.reset();
//		writeToCache(1025, 467, 1, true);
//		System.out.println(Cycles);
//		Cycles.reset();
//		
		Cycles.reset();
		writeToCache(2106, 592, 1, true);
		Cycles.print();
		//Cycles.reset();
		//System.out.println(readFromCache(2008,true));
		//Cycles.print();
		Cycles.reset();
		System.out.println(readFromCache(4007,true));
		Cycles.print();
		Cycles.reset();
		System.out.println(readFromCache(4000,false));
		System.out.println(readFromCache(4001,false));
		System.out.println(readFromCache(4002,false));
		System.out.println(readFromCache(4003,false));
		Cycles.print();
		Cycles.reset();
		System.out.println(readFromCache(4007, true));
		Cycles.print();
		Cycles.reset();
		System.out.println(readFromCache(4000,false));
		Cycles.print();
		Cycles.reset();
		writeToCache(4007, 777, 1, true);
		Cycles.print();
		Cycles.reset();
		System.out.println(readFromCache(4000,true));
		Cycles.print();
		PrintALLMemory();	
		
	}
	
	

}


